Electrically powered vehicles are often used in manufacturing and warehouse environments for transporting and manipulating articles of manufacture. Such vehicles are desirable in such environments due to their clean operation and low noise. Often such vehicles are propelled along a fixed rail or track, allowing precise control of movement along a predetermined path.
In particular, computer controlled materials transport systems are known for moving materials among various work stations of a facility. Such systems are employed, as an example, in semiconductor fabrication facilities for moving semiconductor wafers to successive work stations. In such a wafer transport system, a monorail track is routed past the work stations and a plurality of electric vehicles are mounted on the track and moveable therealong for delivering wafers to successive work stations and for removing wafers therefrom after requisite processing operations have been accomplished. The track is composed of interconnected track sections that usually include one or more routing sections or modules that are operative to provide plural paths along the track. In general a node is a location where a vehicle is stopped, loaded, unloaded, or redirected. Thus, a node can be a workstation that a vehicle must pass through or an intersection of one or more tracks where the vehicle may be redirected.
The vehicles on the track can operate in two modes--connected or semi-independent. In connected operation, a central controller, usually a computer, assigns destinations to vehicles and monitors operation of the whole system even when the vehicles are not at a station.
In the past, the central controller has assigned a route to a vehicle based on a static routing algorithm that typically attempts to find the vehicle having the minimum distance from the destination node. This distance may include a static penalty referred to as a "node crossing value" for each node that the vehicle must pass through on the route to the destination node. However, the static routing algorithms are unable to adjust to exigent circumstances that may exist within the materials transport systems such as traffic congestion and other delays due to equipment. In addition, many computer controlled materials transport systems have at least two levels, or zones. These different levels or zones often have a limited capability for transporting vehicles therebetween. For example, in a two level system the two levels may be connected by a single vertical switch, which due to its height and speed may create an area of traffic congestion.
It would therefore be desirable to be able to compute a vehicle route using a dynamic routing algorithm that is able to respond to exigent circumstances within the materials transport system and that is able to minimize the vehicle traffic between different levels or zones.